/*
这是一个字符串排列问题，考虑使用回溯法
可以分为两部分来做
第一部分：求所有可能在第一个位置的字符，即把第一个字符与后面所有字符交换，包括自己和自己交换
第二部分：固定第一个字符，求后面所有字符的排列，即又回到第一部分
其中注意一个问题：如果第一个字符与后面某一个位置字符相同，则不用交换
*/

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> all;
        if(str.size() == 0){
            return all;
        }
        string tmp;
        recur(str, tmp, all, 0);
        return all;
    }
    void recur(string str, string& tmp, vector<string> &all, int start){
        if(start < 0 || str.size() == 0){
            return;
        }
        if(str.size() == start){
            all.push_back(tmp);
            return;
        }
        for(int i = start; i < str.size(); i++){
            if(i != start && str[i] == str[start]){    //如果字符相同，不用交换
                continue;
            }
            swap(str[i], str[start]);
            tmp +=  str[start];
            recur(str, tmp, all, start + 1);
            tmp.pop_back();            //回溯法的关键
        }
    }
};

